#include <gtest/gtest.h>
#include "common.h"
#include <unordered_map>
#include <queue>

using namespace ::std;

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k);
};

// 先哈希计数，然后插入优先队列
vector<int> Solution::topKFrequent(vector<int>& nums, int k) {
    vector<int> result = {};
    unordered_map<int, int> seen;
    for(auto n : nums) {
        if(seen.find(n) == seen.end()) seen[n] = 1;
        else seen[n]++;
    }
    priority_queue<pair<int, int>> que;
    for(auto& p : seen) que.push(pair<int, int>(p.second, p.first));
    while(k--) {
        result.emplace_back(que.top().second);
        que.pop();
    }
    return result;
}

class TopKFrequentCheck : public ::testing::Test {
public:
	class Solution solution;
};

TEST_F(TopKFrequentCheck, testTopKFrequent_1) {
    vector<int> nums = {1,1,1,2,2,3,3,3,3,3,5,6};
    int k = 3;
    EXPECT_TRUE(vector<int>({3,1,2}) == solution.topKFrequent(nums, k));
}

int main() {
	::testing::InitGoogleTest();
	return RUN_ALL_TESTS();
}
